1. Field of the Invention
This invention relates to the field of computer system utilization where a number of jobs are run periodically on a number of computer systems and, more particularly, to a technique for determining some mix of assignments of jobs to particular computers that will result in near-optimal throughput for the entire set of computer systems.
2. Background Description
There is a great deal of art designed to optimize throughput of a workload on a single computer or even a multiprocessor system. Much of the work on throughput optimization was done in the 1960's and little has changed. Jobs are scheduled for execution based upon a variety of factors: job priority, time of residence in the queue, deadlines, start times, facilities usage, and a host of other factors. Early in the history of writing scheduling and dispatching programs, a variety of ways were developed to assure that all jobs will eventually receive a suitable and effective share of the system resources. For example, to avoid a low-priority job being deferred for an excessive period or never reaching execution, a method of “aging” was devised. By this method, the priority of a job might be increased by some amount every time the job is passed over in the queue. Then, because the job's priority increases over time, eventually the job will be run while not significantly affecting performance of jobs of higher priority.
However, the problem becomes very different from job queuing when applied to a system of multiple computers where the issue is how to assign a number of jobs to a number of different computers so that overall system performance is optimized. Queuing or dispatching systems determine how an individual processor will order tasks to receive facilities, etc. rather than allocating a mix of jobs over a plurality of computers in a computer system or set of computer systems which may differ from each other. It is assumed in regard to such a problem that the jobs are to be run on some periodic basis, such as, once a week, or real-time jobs that are constantly executing in a computer. In such a case, it is to be expected that some allocations of jobs to particular computers will work better than others (e.g. with better utilization of available resource, greater throughput and the like). That being the case, there should be some allocation that works as well as or better than all others which would be the optimum allocation or optimum mix, even though performance may not be guaranteed to be optimum in all circumstances or even to satisfy all performance goals.
The problem of allocation of a number of objects among a number of capacities has led to a number of algorithms known as bin packing, which is well-known in the art of operations research. In the conventional process, items are packed into bins based on the unallocated capacities of the various bins. Further, in the conventional approach, the item packing order is fixed, usually by arranging the items in order of decreasing item size. The items are then packed sequentially as arranged using any one of several bin selection rules, such as, first-fit, best-fit, worst-fit, etc.
However, as applied to the packing of software applications (objects) into computers and associated peripherals of a computer system or network (capacities/bins), known bin packing algorithms are ill-suited to finding an optimum solution due to the number of criteria and parameters which characterize the capacities of a computer (e.g. processor and bus architecture, storage, memory and cache capacities and operating protocols therefor, operating systems, peripherals and interfaces and the like) and the variability of processing time for each particular application in regard to those parameters. These criteria and parameters necessarily have multiple and possibly interdependent values such as may be represented by a vector. That is, when packing scalar items into bins (e.g. when consideration is limited to a single attribute, such as, memory requirements only or, more generally, a “size”) the efficiency of packing (and bin packing algorithms) relative to bin capacity is closely correlated to item size and largely independent of bin capacity if sufficient to a given item. Therefore, good results are often obtained in scalar packing by ordering items in accordance with size. However, when packing vector items, that is, when consideration is expanded to include more than a single attribute, such as, considering memory capacity and port bandwidth, among others, ordering by increasing or decreasing size does not yield comparably good results since the packing depends on numerous attributes of both items and bin capacities. Moreover, while vector attributes may each be quantified, there are no techniques of quantifying vectors in combination to yield any discernible improvement in performance of bin packing algorithms similar to the use of size in scalar bin packing and any computation to develop a quantitative evaluation would be extremely complex since both individual vectors and each combination corresponding to a respective job or task must be accommodated by the bin packing. Thus bin packing techniques become intractably difficult when plural attributes must be considered and no technique has been developed which can significantly affect the likelihood of finding a good solution or improving the efficiency or effectiveness of a bin packing algorithm for vector packing.
Given a number of computer systems and a number of jobs or “items” to be performed, there are many ways to assign the items to computer systems. As the number of systems and the number of items increases, the number of combinations of items and systems grows rapidly. When the number of systems and the number of items is more than a mere handful, there may be very many ways to allocate the items to the systems. The number may be reduced somewhat when certain items have needs for facilities that may not be available on all of the computer systems. For example, a given item may require more memory than some of the computer systems have. That item must be run, if at all, on a system with sufficient memory. Nevertheless, no system or methodology exists at the present state of the art which provides for determination of an optimal allocation of a plurality of different jobs, particularly jobs having different requirements and different performance characteristics over a plurality of computers or computer systems having different hardware and software attributes.